package net.cloudsun.graph.puzzle;

import net.cloudsun.graph.core.*;

import java.io.*;
import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.function.Function;
import java.util.stream.Collectors;

/**
 * 拼图的图
 *
 * @author Ryan
 * @since 1.0
 */
public class JigsawGraph extends UnweightedGraph<JigsawState> {

    /**
     * 3阶拼图的终态
     */
    public static final int FINAL_STATE_INDEX = 181439;
    private Map<JigsawState, Integer> stateIndexMap;

    /**
     * 如果用图算法
     * 拼图假设用数字代替。以3阶为例子
     * 1 2 3
     * 4 5 6
     * 7 8 0
     * 图表化
     * 可以这样
     * ↖ ㊤ ↗
     * ㊧ ㊥ ㊨
     * ↙ ㊦ ↘
     * 状态列表
     * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1
     * 总共362880种状态
     * 可以用图算法解开
     * 怎么存储数据呢？
     * 0~8是9个数字
     * 以4位存储
     * 总共9个数字，需要36位
     * 所以用5个byte就可以存储了
     * 首先造出所有的1088640种状态
     * 先利用排列树生成所有的排列
     * 然后把这些排列放进图中
     * 之后将图的边放进去
     * 加入边
     * 边是最难的
     * 把兄弟加进去
     * 最后就是宽度搜索了
     * 由于每一个状态都有边
     * 可以使用这样的算法
     * 将所有的节点放入hash map key为节点状态，value为索引
     *
     * 对于状态A，求得所有兄弟状态。然后找索引
     */
    public JigsawGraph() {
        JigsawState[] vertices = fromArrangement();
        init(vertices);
    }

    public JigsawGraph(File file) {
        // 从文件反序列化出来
        ArrayList<JigsawState> states = new ArrayList<>(181440);
        try (Scanner in = new Scanner(new BufferedInputStream(new FileInputStream(file)))) {
            while (in.hasNext()) {
                String line = in.nextLine();
                JigsawState state = new JigsawState(line);
                states.add(state);
            }
            vertices = states.toArray(new JigsawState[0]);
            init(vertices);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public JigsawGraph(File vertexfile, File edgesFile) {
        // 从文件反序列化出来
        try (ObjectInputStream in = new ObjectInputStream(new FileInputStream(vertexfile));
             ObjectInputStream edgesIn = new ObjectInputStream(new FileInputStream(edgesFile));
        ) {
            this.vertices = (JigsawState[]) in.readObject();
            this.stateIndexMap = map(vertices);
            this.edges = (UnweightedEdgeList[]) edgesIn.readObject();
        } catch (IOException | ClassNotFoundException e) {
            e.printStackTrace();
        }
    }

    /**
     * @param vertices 通过一个数组进行初始化
     */
    private void init(JigsawState[] vertices) {
        this.vertices = vertices;
        this.stateIndexMap = map(vertices);
        this.edges = getEdgeLists(vertices);
    }

    protected static Map<JigsawState, Integer> map(JigsawState[] vertices) {
        AtomicInteger atomicInteger = new AtomicInteger(0);
        return Arrays.stream(vertices)
                .collect(Collectors.toMap(Function.identity(), x -> atomicInteger.getAndIncrement()));
    }

    protected UnweightedEdgeList[] getEdgeLists(JigsawState[] vertices) {
        return getEdgeLists(vertices, stateIndexMap);
    }

    protected static UnweightedEdgeList[] getEdgeLists(JigsawState[] vertices, Map<JigsawState, Integer> stateIndexMap) {
        UnweightedEdgeList[] allEdge = new UnweightedEdgeList[vertices.length];
        for (int i = 0; i < vertices.length; i++) {
            JigsawState state = vertices[i];
            Map<PuzzleDirection,JigsawState> brothers = state.getBrothers();
            // 组成一个list
            UnweightedEdgeList edges = new UnweightedEdgeList();
            for (Map.Entry<PuzzleDirection,JigsawState> entry : brothers.entrySet()) {
                JigsawState brother = entry.getValue();
                final Integer brotherIndex = stateIndexMap.get(brother);
                // 俞建波 2021年11月23日 修复bug：如果不存在就空指针异常
                if (brotherIndex != null) {
                    PuzzleEdge edge = new PuzzleEdge(i, brotherIndex);
                    // 设置关系
                    edge.setDirection(entry.getKey());
                    edges.add(edge);
                }
            }

            allEdge[i] = edges;
        }
        return allEdge;
    }

    private JigsawState[] fromArrangement() {
        Integer[] integers = {0, 1, 2, 3, 4, 5, 6, 7, 8};
        ArrangementTree<Integer> arrangementTree = new ArrangementTree<>(integers);
        List<List<Integer>> arrangements = arrangementTree.getArrangements();
        return createJigsawVertices(arrangements);
    }

    private JigsawState[] createJigsawVertices(List<List<Integer>> arrangements) {
        JigsawState[] vertices = new JigsawState[arrangements.size()];
        int i = 0;
        for (List<Integer> arrangement : arrangements) {
            JigsawState state = new JigsawState(arrangement);
            int index = i++;
            vertices[index] = state;
        }
        return vertices;
    }

    public List<JigsawState> bfs(JigsawState first, JigsawState finalState) {
        Integer first1 = stateIndexMap.get(first);
        System.out.println("first1 = " + first1);
        Integer finalState1 = stateIndexMap.get(finalState);
        System.out.println("finalState1 = " + finalState1);
        return bfs(first1, finalState1);
    }

    public Set<Integer> bfs(JigsawState first) {
        return bfs(stateIndexMap.get(first));
    }

    public Map<JigsawState, Integer> getStateIndexMap() {
        return stateIndexMap;
    }

    public void setStateIndexMap(Map<JigsawState, Integer> stateIndexMap) {
        this.stateIndexMap = stateIndexMap;
    }
}
